package datastructure.book.dp._1_pathway.all;

public class _1_Solution {

    public int uniquePaths1(int m, int n) {
        return uniquePaths1(m,n,0,0);
    }

    private int uniquePaths1(int m, int n,int i, int j) {
        if (i > m - 1 || j > n - 1) {
            return 0;
        }
        if (i == (m - 1) && j == (n - 1)) {
            return 1;
        }
        return uniquePaths1(m,n,i+1,j)+uniquePaths1(m,n,i,j+1);
    }
    int[][] cntArr;
    public int uniquePaths(int m, int n) {
        cntArr = new int[m][n];
        cntArr[m-1][n-1] = 1;
        uniquePaths(m,n,0,0);
        return cntArr[0][0];
    }

    private boolean uniquePaths(int m, int n,int i, int j) {
        if (i > m - 1 || j > n - 1) {
            return false;
        }
        if (i == m-1 && j == n-1){
            return true;
        }
        if (i + 1 < m) {
            if (cntArr[i + 1][j] != 0) {
                cntArr[i][j] += cntArr[i+1][j];
            }else if (uniquePaths(m,n,i+1,j)){
                cntArr[i][j] += cntArr[i+1][j];
            }
        }
        if (j + 1 < n) {
            if (cntArr[i][j + 1] != 0) {
                cntArr[i][j] += cntArr[i][j+1];
            }else if (uniquePaths(m,n,i,j+1)){
                cntArr[i][j] += cntArr[i][j+1];
            }
        }
        return true;
    }
}
